Given two graphs $G$ and $H$, we investigate for which functions $p=p(n)$ therandom graph $G_{n,p}$ (the binomial random graph on $n$ vertices with edgeprobability $p$) satisfies with probability $1-o(1)$ that everyred-blue-coloring of its edges contains a red copy of $G$ or a blue copy of$H$. We prove a general upper bound on the threshold for this property underthe assumption that the denser of the two graphs satisfies a certainbalancedness condition. Our result partially confirms a conjecture by the firstauthor and Kreuter, and together with earlier lower bound results establishesthe exact order of magnitude of the threshold for the case in which $G$ and $H$are complete graphs of arbitrary size. In our proof we present an alternative to the so-called deletion method,which was introduced by R\"odl and Ruci\'{n}ski in their study of symmetricRamsey properties of random graphs (i.e. the case $G=H$), and has been used inmany proofs of similar results since then.
展开▼
机译：给定两个图$ G $和$ H $，我们调查哪些函数$ p = p（n）$随机图$ G_ {n，p} $（具有边概率$ p $的$ n $顶点的二项式随机图）满足$ 1-o（1）$的概率，其边缘的每个红色蓝色包含$ G $的红色副本或$ H $的蓝色副本。在两个图的稠密性满足一定平衡条件的假设下，我们证明了该属性阈值的一般上限。我们的结果部分证实了第一作者和Kreuter的猜想，并且与更早的下限结果一起为$ G $和$ H $是任意大小的完整图的情况确定了阈值的确切数量级。在我们的证明中，我们提出了一种所谓的删除方法的替代方法，该方法是R \“ odl和Ruci \'{n} ski在研究随机图的对称Ramsey性质时引入的（例如，情况$ G = H $） ，并且从那时起已用于许多类似结果的证明。
展开▼
